/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package tri;

import java.util.ArrayList;
import java.util.List;

/**
 *
 * @author Xuan Huy
 */
public class Fusion {

    private static int nbInversions = 0;

    /**
     * La méthode fusionne les deux listes ordonnées des entiers passées en
     * paramètres en une seule liste ordonnée.
     *
     * @param liste1 une liste ordonnée des entiers.
     * @param liste2 une liste ordonnée des entiers.
     * @return une liste ordonnée, fusion de deux listes <code>liste1</code>
     * et <code>liste2</code>
     */
    public static List<Integer> fusion(List<Integer> liste1, List<Integer> liste2) {
        List<Integer> copy1 = new ArrayList<>(liste1);
        List<Integer> copy2 = new ArrayList<>(liste2);
        List<Integer> resultat = new ArrayList<>();
        while (!copy1.isEmpty() && !copy2.isEmpty()) {
            Integer k;
            /**
             * A cause du calcul du nombre d'inversion, le signe inférieur ou
             * égal est obligatoire.
             */
            if (copy1.get(0).compareTo(copy2.get(0)) <= 0) {
                k = copy1.remove(0);
            } else {
                nbInversions += copy1.size();
                k = copy2.remove(0);
            }
            resultat.add(k);
        }
        if (copy1.isEmpty()) {
            resultat.addAll(copy2);
        } else {
            resultat.addAll(copy1);
        }
        return resultat;
    }

    /**
     * La méthode tri la liste
     * <code>liste</code> passée en paramètre, dans l'ordre croissant, par la
     * méthode de tri fusion.
     *
     * @param liste une liste des entiers qu'il faut ordonner.
     * @return une liste ordonnée des entiers.
     */
    public static List<Integer> triFusion(List<Integer> liste) {
        int taille = liste.size();
        int k = taille / 2;
        if (taille == 0) {
            return new ArrayList<>();
        }
        if (taille == 1) {
            return new ArrayList<>(liste);
        }
        List<Integer> sousListe1 = liste.subList(0, k);
        List<Integer> sousListe2 = liste.subList(k, taille);
        List<Integer> resultat1 = triFusion(sousListe1);
        List<Integer> resultat2 = triFusion(sousListe2);
        List<Integer> resultat = fusion(resultat1, resultat2);
        return resultat;
    }

    /**
     * La méthode retourne le nombre d'inversions de la liste
     * <code>liste</liste> passée à la méthode {@link tri.Fusion#triFusion(java.util.List)}.
     * Cette méthode ne doit être appelée qu'après l'invocation de la méthode
     * {@link tri.Fusion#triFusion(java.util.List)}.
     *
     * @return le nombre d'inversions.
     */
    public static int getNbInversions() {
        return nbInversions;
    }

    /**
     * La méthode permet d'initialiser le nombre d'inversions, qui devrait égal
     * à
     * <code>0</code> avant l'invocation de la méthode
     * {@link tri.Fusion#triFusion(java.util.List)}.
     *
     * @param nbInversions le nombre d'inversions initial.
     */
    public static void setNbInversions(int nbInversions) {
        Fusion.nbInversions = nbInversions;
    }
}
